\chapter{Klasyczne twierdzenia o kolorowaniu wierzchołków}\label{twierdzenia}

\section{Twierdzenia ogólne}\label{general}
\begin{Tw}\label{twierdzenia:general:delplus1}
  Graf prosty w ktorym największy stopień wierzchołka wynosi $\Delta$ jest \newline $(\Delta+1)-kolorowalny$.
\end{Tw}
\emph{Dowód.} Udowodnić to można przez indukcję względem liczby wierzchołków. usuwając wierzchołek (razem z krawedziami incydentnymi z nim) sopnia 
$\Delta$ na pewno nie zwiększymy liczby kolorów potrzebnych do pokolorowania grafu i maksymalny stopień wierzchołka dalej będzie nie większy niż $\Delta$.
Jeśli nawet wszystkie wierzchołki połączone wcześniej z tym który usuneliśmy są różnych kolorów to jest ich najwyżej $\Delta$ więc dodając 
wierzchołek z powrotem pozostaje nam jeszce jedna barwa do wykorzystania.\newline %$\square \box \Box  \blacksquare$ - zaden znaczek nie działa

Nieco silniejszym jest twierdzenie Brooks'a:
\begin{Tw}[Brooks'a]\label{twierdzenia:general:twbrooks}
  Każdy niepełny, spójny graf prosty o maksymalnym stopniu wierchołka $\Delta \geq 3$ jest $\Delta$-kolorowalny. 
  Zaś grafy pełne oraz składające się z cyklu o nieparzystej długości są $(\Delta + 1) $-kolorowalne.
\end{Tw}
\emph{Dowód}  % TODO

\section{Twierdzenia o grafach planarnych}\label{planar}
Na początek przedstawimy dwa twierdzenia o grafach planarnych na których opierają się twierdzenia o kolorowaniu. Ich dowody pominiemy aby zachować 
jednolitość tematu pracy.
\begin{Tw}\label{twierdzenia:planar:twst5}
  W każdym grafie planarnym istnieje wierzchołek o stopniu mniejszym lub rownym 5
\end{Tw}

\begin{Tw}[Kuratowskiego]\label{twierdzenia:planar:kuratowski}
 Graf jest planarny $\Leftrightarrow$ nie zawiera podgrafu homeomorficznego z $K_5$ lub $K_{3,3}$.
\end{Tw}
Dowód pierwszego twierdzenia znaleźć można w książce \cite{wprowadzeniedoteorii}, szkic drugiego zaś w \cite{aspektykombinatoryki}
\newline

Możemy teraz przejść do głównego tematu. Na początek proste do udowodnienia twierdzenie:
\begin{Tw}[o 6-barwach]\label{twierdzenia:planar:tw6barw}
  Każdy graf planarny jest 6-kolorowalny
\end{Tw}
\emph{Dowód.} Twierdzenie to (jak zwykle) udowodnimy przed indukcję względem liczby wierzchołków, będzie to bardzo podobny dowód do \ref{twierdzenia:general:delplus1}. 
Dla grafów o najwyżej 6 wierzchołkach jest to oczywiste. Przy $|V| > 6$ skorzystamy z twierdzenia \ref{twierdzenia:planar:twst5}. Tak więc biorąc wierzchołek 
stopnia 5 (lub mniejszym jeśli taki nie istnieje) i usuwamy go z grafu (jak zwykle ze wszystkimi krawędziami incydentnymi). Oczywiste jest że redukując zbiór  
wierzchołków grafu nie zwiększymy jego liczby chromatycznej więc w założeniu indukcyjnym taki graf bedzie także 6-kolorowalny. Dodając usunięty wierzchołek z 
powrotem mamy dla niego na pewno co najmniej jedną dostępną barwę ponieważ sąsiadów jest co najwyżej pięciu (i nawet nie koniecznie muszą być różnych kolorów).\newline%\square 

Przeprowadzając pewne obserwacje powyższego dowodu można nieco wzmocnić dane twierdzenie.
\begin{Tw}[o 5 barwach]\label{twierdzenia:planar:tw5barw}
 Każdy graf planarny jest 5-kolorowalny
\end{Tw}
\emph{Dowód.} Podobnie jak wyżej wykorzystamy indukcję względem ilości wierzchołków, twierdzenie o istnieniu wierzchołka stopnia $\deg(v) \leq 5$ (tw. \ref{twierdzenia:planar:twst5}) 
a także fakt że grafy planarne nie zawierają kliki $K_5$ (tw. \ref{twierdzenia:planar:kuratowski}). $\square$ 
